package com.wx.learn.sort;

import static com.wx.learn.Common.swap;

/**
 * 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
 *
 * <li>将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；</li>
 * <li>将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；</li>
 * <li>由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。</li>
 *
 * @author wangxin
 */
public class HeapSort {


    public static void heapSort(int[] s) {
        buildHeap(s);
        for (int i = s.length - 1; i > 0; i--) {
            swap(s, 0, i);
            adjustHeap(s, 0, i);
        }
    }

    /**
     * 初始构建大顶堆
     *
     * @param s
     */
    public static void buildHeap(int[] s) {
        for (int i = s.length / 2 - 1; i >= 0; i--) {
            adjustHeap(s, i, s.length);
        }
    }

    /**
     * 调整堆
     *
     * @param s
     * @param i
     * @param length
     */
    public static void adjustHeap(int[] s, int i, int length) {
        int left = 2 * i + 1, right = 2 * i + 2;
        int largest = i;
        if (left < length && s[largest] < s[left]) {
            largest = left;
        }
        if (right < length && s[largest] < s[right]) {
            largest = right;
        }
        if (largest != i) {
            swap(s, i, largest);
            //继续调整子堆为大顶堆
            adjustHeap(s, largest, length);
        }
    }

    public static void main(String[] args) {
        int[] s = {4, 3, 2, 5, 1, 6, 7, 8, 9, 10};
        heapSort(s);
        for (int i = 0; i < s.length; i++) {
            System.out.println(s[i]);
        }
    }

}
